P4451 [国家集训队]整数的lqp拆分

设整数 nnlqp\text{lqp} 拆分权值为 g(n)g(n) , 那么有:

{g(n)=1(n=0)g(n)=i=0n1fib(i)×g(ni)(n=0)\begin{cases} g(n)=1 & (n=0) \\ \displaystyle g(n)=\sum_{i=0}^{n-1} fib(i) \times g(n-i) & (n \not=0) \end{cases}

F(x)F(x) 为斐波拉契数列的 OGF\text{OGF} , G(x)G(x)ggOGF\text{OGF}

卷积就是生成函数的乘法,得到:

G=FG+1G=F*G+1

( 多出来的 11 是让 g(0)=1g(0)=1 的原因 )

又有斐波拉契数列的生成函数:

F(x)=11xx2F(x)=\frac{1}{1-x-x^2}

那么:

G(x)=1xx212xx2G(x)=\frac{1-x-x^2}{1-2x-x^2}

G(x)=1+x12xx2G(x)=1+\frac{x}{1-2x-x^2}

想办法将后面的分数拆开,不妨令 x12xx2=A(1ax11bx1)\frac{x}{1-2x-x^2}=A(\frac{1}{ax-1}-\frac{1}{bx-1})

然后对比系数解出:

{A=24a=1+2b=12\begin{cases} A=\frac{\sqrt 2}{4} \\ a=1+\sqrt{2} \\ b=1-\sqrt{2} \\ \end{cases}

G(x)=1+24(11(1+2)x11(12)x)G(x)=1+\frac{\sqrt 2}{4}(\frac{1}{1-(1+\sqrt{2})x} - \frac{1}{1-(1-\sqrt{2})x})

那么得到:

g(n)=24((1+2)n(12)n)g(n)=\frac{\sqrt 2}{4} ((1+\sqrt {2})^n - (1-\sqrt {2})^n)

经过枚举你发现 259713600(mod1e9+7)\sqrt{2}\equiv 59713600 ( \bmod 1e9+7 )

那么用费马小定理处理指数就可以了。

#include <cstdio>

const int Mod = 1e9 + 7 , Sqrt2 = 59713600;

int Quick_pow( int x , int po ) {
    x = ( x % Mod + Mod ) % Mod;
    int Ans = 1;
    for( ; po ; po >>= 1 , x = 1ll * x * x % Mod )
        if( po & 1 ) Ans = 1ll * Ans * x % Mod;
    return Ans;
}
int Inv( int x ) {
    return Quick_pow( x , Mod - 2 );
}

void Read( int &x ) {
    x = 0; char s = getchar();
    for( ; '0' <= s && s <= '9' ; s = getchar() ) x = ( 10ll * x + s - '0' ) % ( Mod - 1 );
}

int n;
int main( ) {
    Read( n );
    printf("%d\n", ( 1ll * Sqrt2 * Inv( 4 ) % Mod * ( Quick_pow( 1 + Sqrt2 , n ) - Quick_pow( 1 - Sqrt2 , n ) + Mod ) % Mod + Mod ) % Mod );
    return 0;
}